package algorithm.leetcode.simple;

/*
 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
 */

import java.util.ArrayList;
import java.util.List;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/10/14
 */
public class Question118 {

    public static void main(String[] args) {

    }

    public List<List<Integer>> generate(int numRows) {
        // 定义一个结果集
        List<List<Integer>> triangle = new ArrayList<>(numRows);
        if (numRows == 0) {
            return triangle;
        }
        // 第一行
        triangle.add(new ArrayList<>(1));
        triangle.get(0).add(1);
        List<Integer> row;
        for (int i = 1; i < numRows; i++) {
            row = new ArrayList<>(10);
            // 每次当前行依赖于上一行
            List<Integer> preRow = triangle.get(i - 1);
            // 每行第一个值固定1
            row.add(1);
            for (int j = 1; j < i; j++) {
                // 填充
                row.add(preRow.get(j - 1) + preRow.get(j));
            }
            // 每行最后一个值固定1
            row.add(1);
            triangle.add(row);
        }
        return triangle;
    }
}
